import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] arr = new int[][]{{1,1,1}, {1,1,0}, {1,0,1}};
        for(int[] e: s.floodFill(arr, 1, 1, 1)) {
            for(int x: e) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        /**
         * 图像渲染-floodFill算法复习
         * 入队时就修改颜色，故无需使用记录表*/
        // 1 preliminary
        int initialColor = image[sr][sc];
        // -judge boundary conditions
        if(initialColor == color) {
            return image;
        }
        int m = image.length;
        int n = image[0].length;
        int[][] indexMatrix = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        Queue<int[]> queue = new LinkedList<>();
        // -- error: I didn't modify the initial values.
        image[sr][sc] = color;
        queue.offer(new int[]{sr, sc});

        // 2 main logic
        while(!queue.isEmpty()) {
            // -1 pop up elements
            int[] cur = queue.poll();

            // -2 search around and push into the queue
            for(int[] e: indexMatrix) {
                int x = cur[0] + e[0];
                int y = cur[1] + e[1];
                if(x >= 0 && y >= 0 && x < m && y < n && image[x][y] == initialColor) {
                    image[x][y] = color;
                    queue.offer(new int[]{x, y});
                }
            }
        }

        // 3 return
        return image;
    }
}
